package _dp_base;

/**
 * 518. 零钱兑换 II
 */
public class No518 {
    private int[] coins;

    /**
     * 1. 递归
     */
    public int change1(int amount, int[] coins) {
        this.coins = coins;
        int n = coins.length;
        return dfs(n - 1, amount);
    }

    private int dfs(int i, int c) {
        if (i < 0) return c == 0 ? 1 : 0;
        else if (coins[i] > c) return dfs(i - 1, c);
        else return dfs(i - 1, c) + dfs(i, c - coins[i]);
    }

    /**
     * 2. 迭代
     */
    public int change2(int amount, int[] coins) {
        int n = coins.length;

        int[][] f = new int[n + 1][amount + 1];
        f[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < amount + 1; c++) {
                if (coins[i] > c) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = f[i][c] + f[i + 1][c - coins[i]];
            }
        }
        return f[n][amount];
    }

    /**
     * 4. 一维数组
     */
    public int change4(int amount, int[] coins) {
        int[] f = new int[amount + 1];
        f[0] = 1;
        for (int coin : coins) {
            for (int c = coin; c < amount + 1; c++) {
                f[c] = f[c] + f[c - coin];
            }
        }
        return f[amount];
    }
}
